package Solution.problem056;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program Leetcode
 * @description:
 * @author: lishangsheng
 * @create: 2019/05/30 11:34
 */
public class BetterSolution {
    public int[][] merge(int[][] intervals) {
        // sort and then merge
        int[] start = new int[intervals.length];
        int[] end = new int[intervals.length];

        for (int i = 0; i < intervals.length; i++) {
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }

        // sort, O(nlogn)
        Arrays.sort(start);
        Arrays.sort(end);

        // merge intervals
        int startIndex = 0;
        int endIndex = 0;

        List<int[]> result = new ArrayList<int[]>();
        while (endIndex < start.length) {
            if (endIndex + 1 == start.length || (start[endIndex+1]>end[endIndex])) {
                result.add(new int[]{start[startIndex],end[endIndex]});
                startIndex = endIndex + 1;
            }

            endIndex++;
        }

        return result.toArray(new int[result.size()][]);
    }
}
